package 纯数组;

import com.alibaba.fastjson.JSON;
import lombok.Data;

import java.util.ArrayList;
import java.util.Collections;

public class NC37合并区间 {

    /**
     * 给出一组区间，请合并所有重叠的区间。
     * 请保证合并后的区间按区间起点升序排列。
     * 输入
     * [[10,30],[20,60],[80,100],[150,180]]
     * 返回值
     * [[10,60],[80,100],[150,180]]
     */

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        Collections.sort(intervals,(o1,o2)->o1.start-o2.start);

        ArrayList<Interval> result=new ArrayList<>();

        if(intervals.size()<1){
            return result;
        }

        int start=intervals.get(0).start;
        int end=intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            if(end>=intervals.get(i).start){
                //融合
                if(end<intervals.get(i).end) {
                    end = intervals.get(i).end;
                }
            }else{
                //加入结果集
                result.add(new Interval(start,end));
                //更新start+end
                start=intervals.get(i).start;
                end=intervals.get(i).end;
            }
        }

        if(result.size()==0||end!=result.get(result.size()-1).end){
            result.add(new Interval(start,end));
        }

        return result;
    }

    @Data
    private static class Interval {
      int start;
      int end;
      Interval() { start = 0; end = 0; }
      Interval(int s, int e) { start = s; end = e; }
    }

    public static void main(String[] args) {
        ArrayList<Interval> list=new ArrayList<>();
        list.add(new Interval(1,4));
        list.add(new Interval(0,6));
        NC37合并区间 n=new NC37合并区间();
        ArrayList<Interval> result = n.merge(list);
        System.out.println(JSON.toJSONString(result));
    }

}